Section: Software

CADO-NFS

Participants : Jérémie Detrey, Pierrick Gaudry, Lionel Muller, Emmanuel Thomé [contact] , Paul Zimmermann.

Cado-nfs is a program to factor integers using the Number Field Sieve algorithm (NFS), developped in the context of the ANR-CADO project (November 2006 to January 2010).

NFS is a complex algorithm which contains a large number of sub-algorithms. The implementation of all of them is now complete, but still leaves some places to be improved. Compared to existing implementations, the Cado-nfs implementation is already a reasonable player. Several factorizations have been completed using our implementations.

Since 2009, the source repository of Cado-nfs is publicly available for download. On October 28, 2011, the 1.1 version of Cado-nfs has been released. Several improvements to the program have been obtained, in practically all areas of the program. In particular, the polynomial selection code described by Thorsten Kleinjung at the CADO workshop in 2008 is now used within Cado-nfs , together with some efficient root-sieve code written by Shi Bai (Australian National University). Overall, Cado-nfs keeps improving its competitivity over alternative code bases. The lattice siever now supports a sieving region of $2^{31}$ ($I=16$); its code has been deeply reorganized to allow future improvements that we have in mind but were difficult to implement (proper sieving of powers, sieve according to the parities of the coordinates of the location). The executables in the linear algebra step have been reorganized (now using shared libraries), and now use a code generation mechanism built on top of the Mpfq library for the arithmetic parts. This is in particular meant to ease future accomodation of other base fields that $\mathrm{GF}\left(2\right)$, which is a requirement for adapting Cado-nfs to discrete logarithm computation. The MPI performance of the linear algebra code has been optimized. Some experimental scripts have been added to execute the sieve on a cluster; these scripts rely on the OAR job scheduler being used, and exploit its “besteffort” mode.

The largest factorizations performed by Cado-nfs in 2011 are a 170-digit integer from aliquot sequence 660 and a 171-digit integer from aliquot sequence 966.